package com.rr.learningdemo.sort;

/**
 * @author RR
 * @date 2021/3/13 23:28
 */
public class FastSort {
    private static void sort(int[] a, int l, int r) {
        int i = l;
        int j = r;
        int temp = a[i];
        while (i < j) {
            //因为左边为第一个坑，所有从右边开始找数填坑
            while (i < j && temp > a[j]) {
                j--;
            }
            //填完一个坑记得移一下下标
            if (i < j) {
                a[i] = a[j];
                i++;
            }
            //跟上面差不多道理
            while (i < j && temp <= a[i]) {
                i++;
            }
            if (i < j) {
                a[j] = a[i];
                j--;
            }
        }
        //记得把最中间的坑填了
        a[i] = temp;
        //分成两段，继续分
        if (i - 1 > l) {
            sort(a,l,i-1);
        }
        if (i + 1 < r) {
            sort(a, i + 1, r);
        }
    }

    public static void main(String[] args) {
//        int[] a = {5, 7, 3, 4, 9, 6, 1};
        int[] a = {10, 14, 17, 16};
        sort(a, 0, a.length - 1);
        for (int i:a){
            System.out.print(i + "-->");
        }
    }
}

